package org.hot100_1;

import java.util.ArrayList;
import java.util.List;

public class leetcode54 {
//    List<String> res = new ArrayList<>();
//    StringBuilder str = new StringBuilder();
//    public List<String> generateParenthesis(int n) {
//
//        backtracking(n,0,0);
//        return res;
//    }
//
//    //left表示左括号的数量、right表示右括号的数量
//    //只有当left>right时，添加括号才算有效
//    private void backtracking(int n ,int left,int right){
//        if (str.length()==2*n){
//            res.add(new String(str));
//            return;
//        }
//
//        if (left<n){
//            str.append("(");
//            backtracking(n,left+1,right);
//            str.deleteCharAt(str.length()-1);
//        }
//
//        if (right<left){
//            str.append(")");
//            backtracking(n,left,right+1);
//            str.deleteCharAt(str.length()-1);
//        }
//    }

    List<String> res = new ArrayList<>();
    StringBuilder sb =new StringBuilder();
    public List<String> generateParenthesis(int n) {
        backtracking(n,0,0);
        return res;
    }

    private void backtracking(int n,int leftNum,int rightNum){
        if (sb.length()==n*2){
            res.add(new String(sb));
            return;
        }

        if (leftNum<n){
            sb.append("(");
            backtracking(n,leftNum+1,rightNum);
            sb.deleteCharAt(sb.length()-1);
        }

        if (rightNum<leftNum){
            sb.append(")");
            backtracking(n,leftNum,rightNum+1);
            sb.deleteCharAt(sb.length()-1);
        }
    }

}
